package LeetCode1;

import java.util.Deque;
import java.util.LinkedList;

//从先序遍历还原二叉树
public class Num1028 {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> path = new LinkedList<TreeNode>();
        //用来记录走到字符串的位置
        int pos = 0;
        while (pos < traversal.length()) {
            //记录同一次'-'出现的次数，以此来判断深度
            int level = 0;
            //走到下一个值位置
            while (pos < traversal.length() && traversal.charAt(pos) == '-') {
                pos++;
                level++;
            }
            int value = 0;
            //获取当前位置的值
            while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) {
                value = value * 10 + (traversal.charAt(pos) - '0');
                pos++;
            }
            TreeNode node = new TreeNode(value);
            //判断该节点在的位置
            if (level == path.size()) {
                //等于长度说明是栈的的左子节点
                if (!path.isEmpty()) {
                    path.peek().left = node;
                }
            } else {
                //不等于说明跟栈顶同级或者是其，更高一级的树
                while (level != path.size()) {
                    path.pop();
                }
                //走到相同，是其栈顶的右子树（因为是先序，所以左子树最开始被读取过）
                path.peek().right = node;
            }
            //当前节点进栈
            path.push(node);
        }
        //所有元素出栈，只留栈底元素，根节点
        while (path.size() > 1) {
            path.pop();
        }
        return path.peek();
    }
}
